/**
 * 148. 排序链表
 * https://leetcode-cn.com/problems/sort-list/
 */
public class Solutions_148 {
    public static void main(String[] args) {
//        int[] nums = {4, 2, 1, 3};  // output: {1, 2, 3, 4}
        int[] nums = {4, 2, 5, 1, 3};  // output: {1, 2, 3, 4, 5}
//        int[] nums = {-1, 5, 3, 4, 0};  // output: {-1, 0, 3, 4, 5}
//        int[] nums = {};  // output: {}

        ListNode head = MyLinkedListUtils.ArrayToListNode(nums);
        ListNode result = sortList(head);
        System.out.println(MyLinkedListUtils.ListNodeToString(result));
    }

    /**
     * 思路：
     * 1.分治思想，将整个链表划分为前后链表，再对前后链表递归调用完成分割
     *      递归结束条件：子链表只有一个结点，无法分割
     * 2.再使用合并排序的方法，对两个子链表进行合并，合并完成即是有序链表了
     */
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            // 递归结束条件：链表仅有一个结点
            return head;
        }
        // 将 head 分割成前后两个链表，pre 记录要截断处结点的前一个结点
        ListNode fast = head, slow = head;
        // 找到链表的中间结点，链表长度为偶数时，中间结点后面的链表长度为总长度 / 2，方便截断链表
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 截断链表：慢指针后一结点成为新的链表头结点
        ListNode rightHead = slow.next;
        slow.next = null;
        // 前半部分链表头结点为 head
        ListNode l = sortList(head);
        // 后半部分链表头结点为 right
        ListNode r = sortList(rightHead);
        // 合并两个链表
        return merge(l, r);
    }

    /**
     * 按元素升序合并两个链表
     */
    public static ListNode merge(ListNode left, ListNode right) {
        // 建立虚拟头结点
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        // 剩余的结点，直接拼接到 cur 结点后面
        if (left != null) {
            cur.next = left;
        } else if (right != null) {
            cur.next = right;
        }
        return dummyHead.next;
    }
}
